package com.company.ljh.easy;
/**
 * 两个链表的第一个公共节点
 * 输入两个链表，找出它们的第一个公共节点。
 * 若果没有公共节点，返回null
 */

import com.company.ljh.utils.ListNode;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2022/6/10 14:18
 * @version:1.0
 */
public class 两个链表的第一个公共节点 {
    //双指针长度差值辣鸡法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode indexA = headA;
        ListNode indexB = headB;
        //保存两个链表的长度差值
        int sizeA = 0;
        int sizeB = 0;
        while(indexA != null){
            indexA = indexA.next;
            sizeA++;
        }
        while(indexB != null){
            indexB = indexB.next;
            sizeB++;
        }
        int temp = sizeA - sizeB;
        indexA = headA;
        indexB = headB;
        if(temp > 0){
            //A链表先走tmep步
            for(int i =0;i<temp;i++){
                indexA = indexA.next;
            }

        }else{
            for(int i =0;i<-temp;i++){
                indexB = indexB.next;
            }
        }

        while(indexA != indexB){
            if(indexA == null || indexB== null){
                return null;
            }
            indexA = indexA.next;
            indexB = indexB.next;
        }
        return indexA;
    }
    //双指针直接遍历法
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

}
